package com.dbh.alg.algorithm.sort;

import java.util.Arrays;

/**
 * 最大堆
 *
 * @author dongbanghui
 * @date 2020/01/06
 */
public class MaxHeap {

    /**
     * 堆的容量
     */
    private int capacity;

    /**
     * 堆的实际存储数据空间
     */
    private int size;

    /**
     * 内部数组元素
     */
    private int[] arr = {};

    /**
     * 初始化
     * @param capacity
     */
    public MaxHeap(int capacity){
        this.capacity = capacity;
        arr = new int[capacity+1];
    }

    public MaxHeap(int[] arr, int n){
        if(arr.length>0){
            this.capacity = n;
            this.size = n;
            this.arr = new int[capacity+1];
            for(int i=0; i<n; i++){
                this.arr[i+1] = arr[i];
            }
            for (int i=parent(n); i>=1;i--){
                shifDown(i);
            }
        }
    }

    /**
     * 返回当前节点的父节点的索引
     * @param k
     * @return
     */
    private int parent(int k){
        return k/2;
    }

    /**
     * 返回当前节点的左孩子节点的索引
     * @param k
     * @return
     */
    private int leftChild(int k){
        return 2*k;
    }

    /**
     * 返回当前节点的右孩子节点的索引
     * @param k
     * @return
     */
    private int rightChild(int k){
        return 2*k+1;
    }

    /**
     * 向上移动调整堆元素
     * @param k
     */
    private void shifUp(int k){
        while(k>1 && arr[parent(k)]<arr[k]){
            swap(arr, parent(k), k);
            k = parent(k);
        }
    }

    /**
     * 向下移动调整堆元素
     * @param k
     */
    private void shifDown(int k){
        while(leftChild(k)<=size){
            int j = leftChild(k);
            if (j+1<=size && arr[j+1]>arr[j]){
                j++;
            }
            if (arr[k]>=arr[j]){
                break;
            }
            swap(arr, k, j);
            k = j;
        }
    }


    /**
     * 交换数组中两个元素
     * @param arr
     * @param a
     * @param b
     */
    private void swap(int[] arr, int a, int b){
        arr[a] = arr[a] ^ arr[b];
        arr[b] = arr[a] ^ arr[b];
        arr[a] = arr[a] ^ arr[b];
    }

    /**
     * 判断堆是否为空
     * @return
     */
    public boolean isEmpty(){
        return size==0;
    }

    /**
     * 元素大小
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 插入元素
     * @param num
     */
    public void insert(int num){
        arr[size+1] = num;
        size++;
        shifUp(size);
    }

    /**
     * 返回最大值
     * @return
     */
    public int extractMax(){
        int max = 0;
        if(!isEmpty()){
            max = arr[1];
            arr[1] = arr[size];
            size--;
            shifDown(1);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {15, 17, 19, 52, 28, 16, 22, 13, 41, 30, 62};
        int n = arr.length;
//        MaxHeap maxHeap = new MaxHeap(n);
//        for(int i=0; i<n; i++){
//            maxHeap.insert(arr[i]);
//        }
//        for(int i=n-1; i>=0; i--){
//            arr[i] = maxHeap.extractMax();
//        }
        MaxHeap maxHeap = new MaxHeap(arr, n);
        for(int i=n-1; i>=0; i--){
            arr[i] = maxHeap.extractMax();
        }
        System.out.println(Arrays.toString(arr));


    }

}
